#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
vector <int> map[10000+2];
vector <int> ans;
bool s[10000+2];
void dfs(int now)
{
	ans.push_back(now);
	s[now]=1;
	for(int i=0;i<map[now].size();i++)
	{
		if(s[map[now][i]]==0)
		{
			dfs(map[now][i]);
		}
	}
}
void print(vector <int> out)
{
	for(int i=0;i<out.size()-1;i++) printf("%d-",out[i]);
	printf("%d\n",out[out.size()-1]);
	ans.clear();
}
void bfs()
{
	queue <int> que;
	for(int j=1;j<=n;j++)
	{
		if(s[j]==0) que.push(j);
		while(!que.empty())
		{
			if(s[que.front()]==0)
			ans.push_back(que.front());
			s[que.front()]=1;
			for(int i=0;i<map[que.front()].size();i++)
			{
				if(s[map[que.front()][i]]==0)
				{
					que.push(map[que.front()][i]);	
				}
			}
			que.pop();
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int i,j;
	while(m--)
	{
		scanf("%d%d",&i,&j);
		map[i].push_back(j);
		map[j].push_back(i);
	}
	for(int ii=1;ii<=n;ii++)
	{
		sort(map[ii].begin(),map[ii].end());
	}
	dfs(1);
	for(int ii=1;ii<=n;ii++)
	{
		if(s[ii]==0) ans.push_back(ii);
	}
	print(ans);
	memset(s,0,sizeof(s));
	bfs();
	print(ans);
	return 0;
}

